# 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的
# 根节点的引用。
#
#  一般来说，删除节点可分为两个步骤：
#  首先找到需要删除的节点；
#  如果找到了，删除它。
#
#  示例 1:
# 输入：root = [5,3,6,2,4,null,7], key = 3
# 输出：[5,4,6,2,null,null,7]
# 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
# 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
# 另一个正确答案是 [5,2,6,null,4,null,7]。
#
#  示例 2:
# 输入: root = [5,3,6,2,4,null,7], key = 0
# 输出: [5,3,6,2,4,null,7]
# 解释: 二叉树不包含值为 0 的节点
#
#  示例 3:
# 输入: root = [], key = 0
# 输出: []
from com.example.tree.tree_node import TreeNode
from typing import Optional


class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:  # 当前节点的值等于key
            if not root.left and not root.right:  # 节点是叶子节点，直接将该节点指向None即可
                root = None
            elif root.right:  # 节点存在右子节点：先将节点可以由其后继节点进行替代,然后从当前节点的右节点递归删除后继节点
                root.val = self.successor(root)
                root.right = self.deleteNode(root.right, root.val)
            else:  # 节点只有左子节点：先将节点可以由其前驱节点进行替代,然后从当前节点的左节点递归删除前驱节点
                root.val = self.predecessor(root)
                root.left = self.deleteNode(root.left, root.val)
        return root

    def predecessor(self, node: Optional[TreeNode]) -> int:
        node = node.left
        while node.right:
            node = node.right
        return node.val

    def successor(self, node: Optional[TreeNode]) -> int:
        node = node.right
        while node.left:
            node = node.left
        return node.val


if __name__ == "__main__":
    #                    5
    #            3                6
    #        2        4                 7
    #    0
    # -1    1
    root = TreeNode(5)
    root.left, root.right = TreeNode(3), TreeNode(6)
    root.left.left, root.left.right, root.right.right = TreeNode(2), TreeNode(4), TreeNode(7)
    root.left.left.left = TreeNode(0)
    root.left.left.left.left, root.left.left.left.right = TreeNode(-1), TreeNode(1)
    res = Solution().deleteNode(root, 2)
    queue = [res]
    lst = []
    while queue:
        tmp = queue[0]
        lst.append(tmp.val)
        if tmp.left:
            queue.append(tmp.left)
        if tmp.right:
            queue.append(tmp.right)
        del queue[0]
    print(lst)
